#include <bits/stdc++.h>
#ifndef DEBUG
#define debug
#endif
using namespace std;
using i64 = int64_t;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n;
  while (cin >> n) {
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++) cin >> a[i];
    vector<int> sum(n + 1);
    partial_sum(a.begin(), a.end(), sum.begin());
    vector<vector<int>> dp(n + 2, vector<int>(n + 2));
    vector<vector<int>> opt(n + 2, vector<int>(n + 2));
    for (int l = n; l >= 1; l --) {
      dp[l][l] = 0;
      opt[l][l] = l;
      for (int r = l + 1; r <= n; r ++) {
        dp[l][r] = INT_MAX;
        for (int k = opt[l][r - 1]; k <= opt[l + 1][r]; k ++) {
          int v = dp[l][k - 1] + dp[k + 1][r] + sum[r] - sum[l - 1] - a[k];
          if (v < dp[l][r]) {
            dp[l][r] = v;
            opt[l][r] = k;
          }
        }
      }
    }
    cout << dp[1][n] << endl;
  }
}

